package org.example.SolutionNew003;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class DoubleTree001 {
    public static void main(String[] args) {
        DoubleTree001 dt = new DoubleTree001();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(dt.inorderTraversal(root));
    }

    List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal1(TreeNode root) {
        midSortTree(root);
        return res;
    }

    public void midSortTree(TreeNode root) {
        if (root == null) return;
        midSortTree(root.left);
        res.add(root.val);
        midSortTree(root.right);
    }

    //迭代
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root=stack.pop();
            res.add(root.val);
            root=root.right;
        }
        return res;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode predecessor;

        while(root!=null){
            if(root.left!=null){
                predecessor = root.left;
                while(predecessor.right!=null&&predecessor.right!=root){
                    predecessor = predecessor.right;
                }
                if(predecessor.right==null){
                    predecessor.right = root;
                    root = root.left;
                }else{
                     res.add(root.val);
                     predecessor.right = null;
                     root = root.right;
                }
            }else{
                res.add(root.val);
                root=root.right;
            }
        }
        return res;
    }
}
